#include <iostream>
#include <vector>
using namespace std;

void quilkSort(vector<int>& vecArr,int start,int end){
	
	if(start<end){
		int base=vecArr[start];
		int left=start;
		int right=end;
		while(left<right){
			while(right>left && vecArr[right]>=base){
				--right;
			}
			vecArr[left]=vecArr[right];
			while(left<right && vecArr[left]<=base){
				++left;
			}	
			vecArr[right]=vecArr[left];	
		}
		vecArr[left]=base;
		quilkSort(vecArr,start,left-1);
		quilkSort(vecArr,left+1,end);
	}
}
void Print(const vector<int>& vecArr){
	
	for(int i=0;i<vecArr.size();++i){
		cout<<vecArr[i]<<' ';
	}
	cout<<endl;
}
int main(){
	
	vector<int> vecArr({2,1,5,7,5,9});
	Print(vecArr);
	quilkSort(vecArr,0,vecArr.size()-1);
	Print(vecArr);
	return 0;
}
